`
https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
`

/**
 * // Definition for a _Node.
 * function _Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {_Node} root
 * @return {_Node}
 */
var connect = function (root) {
  const stk = []
  stk.push(root)
  // 存储上一次遍历的结点
  let lastNode = null

  while (stk.length) {
    // 每次只遍历当前一层
    const sz = stk.length

    for (let i = 0; i < sz; i++) {
      // 获取当前结点
      const node = stk.shift()
      if (!node) continue

      // 左右子结点入栈
      stk.push(node.left)
      stk.push(node.right)

      // 上一个遍历的结点的 next 指向当前遍历的结点
      if (lastNode) lastNode.next = node
      // 更新上一个存储的结点，给下一个结点用
      lastNode = node
    }

    // 当前一层遍历结束，重置存储的上一个的结点
    lastNode = null
  }
  return root
};